﻿using System.Diagnostics.CodeAnalysis;
/// <summary>
/// https://leetcode-cn.com/problems/combination-sum/
/// </summary>
public class Solution
{
    private class SortedIntListComparer : IEqualityComparer<IList<int>>
    {
        public bool Equals(IList<int>? x, IList<int>? y)
        {
            if (x == null)
                return y == null;
            if (y == null)
                return false;
            return x.SequenceEqual(y);
        }

        public int GetHashCode([DisallowNull] IList<int> obj)
        {
            var result = new HashCode();
            foreach (var item in obj)
                result.Add(item);
            return result.ToHashCode();
        }
    }


    public IList<IList<int>> CombinationSum(int[] candidates, int target)
    {
        var result = new HashSet<IList<int>>(new SortedIntListComparer());
        foreach (var c in this.Combination(candidates, target))
        {
            var list = new List<int>(c);
            list.Sort();
            _ = result.Add(list);
        }
        return new List<IList<int>>(result);
    }

    public IEnumerable<IEnumerable<int>> Combination(int[] candidates, int target)
    {
        List<IEnumerable<int>> result = new List<IEnumerable<int>>();
        foreach (var candidate in candidates)
        {
            var delta = target - candidate;
            if (delta > 0)
            {
                var cs = this.Combination(candidates, delta);
                foreach (var c in cs)
                    result.Add(c.Concat(new int[] { candidate }));
            }
            else if (delta == 0)
                result.Add(new int[] { candidate });
            else // if (delta > 0)
                continue;
        }
        return result;
    }
}